/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 10, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given an array of strings, return all groups of strings that are
 *              anagrams.
 * 
 *              Note: All inputs will be in lower-case.
 */
public class Anagrams {

	public ArrayList<String> anagrams(String[] strs) {
		ArrayList<String> res = new ArrayList<String>();
		if (strs.length < 2)
			return res;
		Arrays.sort(strs, comparator);
		boolean next = false;
		for (int i = 0; i < strs.length - 1; i++) {
			if (equal(strs[i], strs[i + 1])) {
				res.add(strs[i]);
				next = true;
			} else if (next) {
				res.add(strs[i]);
				next = false;
			}
		}
		if (next)
			res.add(strs[strs.length - 1]);
		return res;
	}
	
	public boolean equal(String o1, String o2) {
		char[] c1 = o1.toCharArray();
		char[] c2 = o2.toCharArray();
		if (c1.length != c2.length)
			return false;
		Arrays.sort(c1);
		Arrays.sort(c2);
		for (int i = 0; i < c1.length; i++) {
			if (c1[i] != c2[i])
				return false;
		}
		return true;
	}
	
	public static Comparator<String> comparator = new Comparator<String>() {
		
		@Override
		public int compare(String o1, String o2) {
			char[] c1 = o1.toCharArray();
			char[] c2 = o2.toCharArray();
			if (c1.length < c2.length)
				return -1;
			if (c1.length > c2.length)
				return 1;
			Arrays.sort(c1);
			Arrays.sort(c2);
			for (int i = 0; i < c1.length; i++) {
				if (c1[i] < c2[i])
					return -1;
				if (c1[i] > c2[i])
					return 1;
			}
			return 0;
		}
	};

	@Test
	public void test() {
		String[] strs = new String[] {"dog", "god", "tac", "cat", "tom", "dgo"};
		System.out.println(anagrams(strs));
	}
}
